# 暴力解法
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        ans  = 0
        n = len(s)
        for i in range(n):
            cnt1 = 0
            cnt0 = 0
            for j in range(i, n):
                if s[j] == "1":
                    cnt1 += 1
                else:
                    cnt0 += 1
                if cnt1 >= cnt0 * cnt0:
                    ans += 1
        
        return ans
#
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        n = len(s)
        pre = [-1] * (n + 1)
        for i in range(n):
            if i == 0 or s[i - 1] == '0':
                pre[i + 1] = i
            else:
                pre[i + 1] = pre[i]

        res = 0
        for i in range(1, n + 1):
            cnt0 = 1 if s[i - 1] == '0' else 0
            j = i
            while j > 0 and cnt0 * cnt0 <= n:
                cnt1 = (i - pre[j]) - cnt0
                if cnt0 * cnt0 <= cnt1:
                    res += min(j - pre[j], cnt1 - cnt0 * cnt0 + 1)
                j = pre[j]
                cnt0 += 1
        return res